public class MyDoubleList {
    static class Node {
        int val;
        Node prev, next;

        Node(int val) {
            this.val = val;
        }
    }

    Node head;
    int size;

    public MyDoubleList() {
        System.out.println("---初始化链表---");
        System.out.println("head=" + String.format("%12d", System.identityHashCode(head)));
    }

    void addFirst(int val) {
        Node newNode = new Node(val);
        if (head == null) {
            head = newNode;
            head.next = head;
            head.prev = head;
        } else {
            newNode.next = head;
            newNode.prev = head.prev;
            head.prev.next = newNode;
            head.prev = newNode;
            head = newNode;
        }
        size++;
    }

    void addLast(int val) {
        if (head == null) {
            addFirst(val);
            return;
        }
        Node newNode = new Node(val);
        newNode.next = head;
        newNode.prev = head.prev;
        head.prev.next = newNode;
        head.prev = newNode;
        size++;
    }

    boolean remove(int val) {
        if (head == null) return false;

        Node curr = head;
        do {
            if (curr.val == val) {
                if (size == 1) {
                    head = null;
                } else {
                    curr.prev.next = curr.next;
                    curr.next.prev = curr.prev;
                    if (curr == head) head = head.next;
                }
                size--;
                return true;
            }
            curr = curr.next;
        } while (curr != head);

        return false;
    }

    void reverse() {
        if (head == null || size == 1) return;

        Node curr = head;
        do {
            Node temp = curr.next;
            curr.next = curr.prev;
            curr.prev = temp;
            curr = temp;
        } while (curr != head);

        head = head.next;
    }

    void print() {
        if (head == null) {
            System.out.println("空链表");
            return;
        }
        Node curr = head;
        StringBuilder sb = new StringBuilder();
        do {
            sb.append(curr.val);
            if (curr.next != head) sb.append("，");
            curr = curr.next;
        } while (curr != head);
        System.out.println(sb);
    }

    public static void main(String[] args) {
        MyDoubleList list = new MyDoubleList();

        System.out.println("--- 增加结点（头插法）---");
        list.addFirst(13);
        list.addFirst(14);
        list.addFirst(15);
        list.print();
        System.out.println("length: " + list.size);

        System.out.println("--- 增加结点（尾插法）---");
        list.addLast(21);
        list.addLast(22);
        list.addLast(23);
        list.print();
        System.out.println("length: " + list.size);

        System.out.println("---删除结点---");
        System.out.println("删除数据为5120的结点");
        System.out.println("删除前：");
        list.print();
        boolean result1 = list.remove(5120);
        System.out.println("---删除" + (result1 ? "成功" : "失败"));
        list.print();
        System.out.println("length: " + list.size);

        System.out.println("---删除数据为13的结点");
        System.out.println("删除前：");
        list.print();
        boolean result2 = list.remove(13);
        System.out.println("---删除" + (result2 ? "成功" : "失败"));
        list.print();
        System.out.println("length: " + list.size);

        System.out.println("---删除数据为23的结点");
        System.out.println("删除前：");
        list.print();
        boolean result3 = list.remove(23);
        System.out.println("---删除" + (result3 ? "成功" : "失败"));
        list.print();
        System.out.println("length: " + list.size);

        System.out.println("---反转链表---");
        System.out.println("反转前");
        list.print();
        list.reverse();
        System.out.println("---反转后");
        list.print();
    }
}
